/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.hard._51;

import java.util.ArrayList;
import java.util.List;

/**
 * n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * <p>
 * 上图为 8 皇后问题的一种解法。
 * <p>
 * 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
 * <p>
 * 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 * <p>
 * 示例:
 * <p>
 * 输入: 4
 * 输出: [
 * [".Q..",  // 解法 1
 * "...Q",
 * "Q...",
 * "..Q."],
 * <p>
 * ["..Q.",  // 解法 2
 * "Q...",
 * "...Q",
 * ".Q.."]
 * ]
 * 解释: 4 皇后问题存在两个不同的解法。
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.hard._51
 * @ClassName: NQueens
 * @Author: linyaonan
 * @Date: 2020/1/21 11:29
 */
public class NQueens {
    public List<List<String>> solveNQueens(int n) {
        // 初始化棋盘
        char[][] queue = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                queue[i][j] = '.';
            }
        }
        List<List<String>> result = new ArrayList<>();
        backTracing(queue, 0, n, result);
        return result;
    }

    // 回溯
    private void backTracing(char[][] queue, int row, int n, List<List<String>> result) {
        if (row == n) {
            result.add(charToList(queue));
            return;
        }

        // 一行中的每一个位置
        for (int i = 0; i < queue[0].length; i++) {
            if (isValid(queue, row, i)) {
                // 可以修改为Q位置
                queue[row][i] = 'Q';
                // 递归下一行
                backTracing(queue, row + 1, n, result);
                // 回溯修改为空位置
                queue[row][i] = '.';
            }
        }
    }

    /**
     * 数组转集合
     *
     * @param queue
     * @return
     */
    private List<String> charToList(char[][] queue) {
        List<String> str = new ArrayList<>();
        for (char[] chars : queue) {
            str.add(new String(chars));
        }
        return str;
    }

    /**
     * 校验位置是否可以放置皇后
     *
     * @param queue
     * @param x
     * @param y
     * @return
     */
    private boolean isValid(char[][] queue, int x, int y) {
        for (int i = 0; i <= x; i++) {
            for (int j = 0; j < queue[0].length; j++) {
                // 找出Q的位置，并且Q相关的45与135度不能有x，y的坐标
                if (queue[i][j] == 'Q' && (j == y || Math.abs(x - i) == Math.abs(y - j))) {
                    return false;
                }
            }
        }
        return true;
    }

}
